In wireless networks, the ability to correctly receive data packets with increased reliability is important. Typically, if a packet is lost in transmission, the intended recipient requests that the sender retransmit the packet. However, certain systems that utilize a wireless network may require a very low packet loss and retransmission rate, for example where the data being transmitted via the wireless network is critical to the safety or performance of the system. In these systems, packet loss leading to requests for retransmission is unacceptable.
Network coding is a technique that can be used to improve the capacity and efficiency of network transmissions. Network coding functions by transmitting an encoded function of the data bits rather than the original data bits; subsequently, the function of the data bits is decoded to obtain the original data bits. Transmitting functions of the data bits in this manner can reduce the average number of transmissions needed for a given amount of information, which reduces the number of retransmissions needed if there are bit errors or erasures.
Applying a linear network code to a set of packets results in a greater number of packets than originally contained in the set of packets. Although the extra packets that result from the application of the linear network code usually enable the recipient to successfully decode and recover the original packets, certain network codes are still unable to decode the packets even when only a few packets are lost during transmission. When these systems do not receive enough packets to successfully decode the original packets, they must request packet retransmissions, which decreases system performance and reliability. However, if the decoder for the linear network codes is designed to use all the available information at the receiver side of a system, then the number of retransmissions will be reduced, thereby increasing the reliability of the system.